COMP124

File Manager

Keeps track of every file in the system
Provides an abstracted view of files to the user (logical file system) and maps this on to the real organisation of data on disk (physical file system)

File manager performs various tasks for the OS:

• Organises all files into folders (directories)
• Manages the locations of files on disk
• Maps logical structure on to physical locations
• Enforces restrictions on who can access files (permission system)
• Deals with standard file operations (open, close, read, write, delete...)
• Provides standard system calls so other software can use files
• Liaises with the device manager to access physical disks within the system

Disk Drives

• Mechanical Drive (HDD) - magnetic platter with a read/write head that moves across it
• Solid State Drive (SSD) - uses NAND flash chips to store data via electronic circuits
• The OS provides an abstraction layer on top of the physical hardware

Disk Blocks

Disks are based around the idea of blocks

• Each disk is split into blocks of a certain size
• Operating system chooses the block size (typically 4K = 4096 bytes)
• Files fill up one or more blocks
• Only one files can exist in each block
• Space is wasted when a file doesn't fully fill a block

Each physical disk can be divided into separate partitions

• Each partition will be formatted with a particular disk format (eg. FAT)
• This splits the disk (partition) into blocks of equal size
• Disk format and block usage is determined by the file allocation method

Free List & Metadata

Parts of each disk are reserved to store data about the disk and the files on it

• Not all blocks are used for data (so total actual storage size < disk size)
• Some blocks store the free list and other housekeeping information (metadata)
  The free list is a simple bit vector that records which blocks are free (not used)
• 1 means in use; 0 means free
• 8 blocks can be represented by one byte
• File manager can easily see which blocks are available for new files
• Modern disk formats use a much more complex set of metadata (taking more room)

Some disadvantages:

• Can become out of sync with disk if held in memory (needs to be saved regularly)
• Could be huge (160GB disk with 4K block size needs 5MB for the free list)

File Systems and System Calls

Every file system has four parts

• Physical storage on disk - Formatted as FAT, XFS, EXT4, etc.
• Logical naming scheme - File and directory names (and the way they are nested)
• Permissions model - Access control such as the permissions used by Linux
• System calls - Standardised programmatic access to files via the kernel

System calls include fopen, fclose, fread, fwrite, fseek, fflush

• Any program can manipulate data in files through these standard calls
• The same calls can be used regardless of the physical media or disk format
• System calls provide an abstraction of the underlying disk hardware

User programs see the logical view of the file system via these system calls

Logical and Physical Views

Operating Systems provide conveniences to make life easier for us

• Filenames with extensions
• Folder hierarchies with nested folders and files
• Shell with drag and drop to move or copy files
• This is the LOGICAL view of a file system

However, the OS doesn't follow nor need these human conveniences

• Directories and files are just bit patterns stored in blocks of the disk
• OS needs to know which blocks belong to which files
• Metadata about files and block usage is also stored on the disk
• Arrangement and usage of blocks depends on the file allocation method
• This is the PHYSICAL view of a file system

Inodes and Metadata

There must be some way to map the logical view on to physical locations on disk

• We use inodes to point to physical blocks on disk
• Each file has an inode that stores metadata about it
• Also stores block information (eg. start block) according to allocation method
• The inode table needs to be stored on the disk somewhere
• Each disk format has its own housekeeping data that needs to be stored
• The actual capacity of a disk will be reduced by all the space needed for metadata

Actual storage space = Capacity - (Housekeeping data, Free list, Inode table)

File Allocation and Access

There are several ways to allocate files to blocks on a disk

• Contiguous
• Linked
• Indexed
  The disk format (file allocation method) dictates how easy it is to access blocks in a file

Sequential file access

• Starts with the first block in a file
• Reads each block in turn until the required data is found
  Direct file access
• Goes directly to the block that contains the required data
• Skips over earlier blocks in the file

Contiguous Allocation

Each file is allocated across contiguous blocks on the disk (eg. next to each other)
![[Pasted image 20250519014631.png]]

The inode stores the start block number and number of blocks

Advantages

• Fast for sequential access
• Fast for direct access

Disadvantages

• Fragmentation of free blocks
• Might need regular compaction (defragmentation)
• Needs policy for choosing which free blocks to allocate
• Files don't always have room to grow after initial allocation

Linked Allocation

Each block contains a pointer to the next block (similar to a linked list)
Inode table stores start block number, but not number of blocks
Each actual block ends with the number of next block

Advantages

• Easy to grow and shrink files
• No danger of fragmentation of free blocks

Disadvantages

• Blocks are widely dispersed (worse in HDDS)
• Sequential access less efficient
• Direct access even worse (requires N reads to get to block N in the chain)
• Danger of pointer corruption

Indexed Allocation

First block of a file holds the indexes of all other blocks for the file
The inode stores number of the index block, which contains a list of all blocks for the file

Advantages

• Each file's block information is held in one place
• Very efficient for both sequential and direct access

Disadvantages

• Blocks can still be widely dispersed across disk
• Wastes a block for very small files
• Can run out of pointers for large files (might need to chain index blocks)
• Danger of index block becoming corrupted

File Allocation Table (FAT)

Many Windows installations use the FAT disk format

• Splits a physical disk into distinct sections
• Uses indexed allocation but the index blocks are all stored in one place (the FAT)
  The disk is formatted as follows:
• Boot sector - Contains housekeeping data (and bootstrap code on primary disk)
• FAT - Master copy of the index blocks for each file (inode table)
• FAT (copy) - Backup copy of the FAT to help recover from corrupted disks
• Data region - Contains blocks that store the actual content of files
  Many USB sticks use FAT because it can be understood by all major operating systems

Simply put, FAT is an indexed allocation method where the inode table is stored in its own part of the disk

Advantages

• All pointer information held in one place
• Easier to protect
• No need for a separate free list
• Direct access much more efficient

Disadvantages

• Required HDD head to move constantly between FAT area and file area
• Space for FAT must be reserved when disk is formatted
• FAT will become huge for large disks

New Technology File System (NTFS)

Default disk format for new Windows installations since Windows 3.1 (1993)
Uses a master file table (MFT) but the general principle is the same as FAT
Disk is formatted differently to provide many useful new features

• Access control lists (similar to Linux permissions)
• Encryption
• Journaling
• Hard links
• File compression
• System compression
• Sparse files
• Shadow copies
• Disk quotas

Popular File Systems

Windows:

• FAT32
• NTFS
  MacOS:
• APFS - Apple File System
• Can also read/write FAT disks
• Can read NTFS disks but not easily write
  Linux:
• EXT4 (Cannot be read by windows or macOS)
• btrfs
• ZFS

L2

Files Everywhere

The fundamental concept in Unix is that everything is a file, even things you wouldn't expect like sockets, processes, USB ports, printers
This allows us to use the same system calls and commands to access everything
Presents a clean system call interface to applications and developers

Linux File Systems

Users and programs see a unified view of the file system as a tree-like structure of nested directories and files
This is an abstraction (logical representation) because in reality:

• Some parts of the tree might be stored on separate disks
• Some might be stored on a network
• Some might be stored in memory
• Each can be formatted with a different physical disk layout
  The phrase file system is used in two slightly different ways:
• The overall tree-like view of the entire logical structure
• The physical format of each disk

Logical System Tree

The Linux file system tree is a logical structure that could be provided by multiple physical disks, networks, or other devices

• /dev
  • Virtual file system (stored in memory)
  • Each subdirectory maps onto a physical device
• /home
  • Often located on network drives
  • Not available until the system has fully booted
• /proc
  • Virtual file system
  • Stores dynamic data about current processes
    Each part of the logical file system could use a different physical disk format

Root & Boot

There are two directories that need to be available while the system is booting and the kernel is forking its initial processes

• /root
  • Home directory of the super user
  • Cannot be stored with other home directories (May not be mounted yet)
• /boot
  • Stores kernel image and other required files
  • Bootloader knows where it is and how to read its files

Other parts of the logical file system are mounted in the correct place by the kernel after it has finished loading
You can use the df command to see mount points and physical disks

The EXT4 File System

EXT4 is the most common Linux file system
It can support very large disk and file sizes

• Disks up to 1 exabyte (1 billion GB)
• Individual files up to 16 terabytes
• Standard disk block size is 4KB (but can go up to 64KB)
  Provides several features that improve performance, stability and security

EXT4 Block Groups

EXT4 uses the concept of block groups

• Free block bitmap (free list) is stored in just one block
• Free inode bitmap is stored in another single block
• 4KB block size implies each bitmap can hold 32,768 records
• Enough blocks to store 128MB of actual data
  A disk will be split into many of these small block groups
• Each group will be 128MB in size
• Each will need its own free block and free inode lists
• The first portion of the disk will be used to store all this metadata
• The inodes themselves will also be stored alongside the free lists
• Rest of the disk is used for actual storage of data

EXT4 Physical Disk Format

Superblock at start of disk
Group descriptors block
Data bitmap / Inode bitmap / Inode tables for each block group
File storage area split into blocks

Inode Data Structure

Every file (and directory) has an inode associated with it

• Inodes are stored in the inodes table
• Which inodes are free/used is stored in the inodes bitmap
  Each file inode stores
• Size of file on disk
• Owner, group, and octal permissions value
• Type of inode (file, directory, symbolic link, etc.)
• Timestamps (created, modified, accessed)
• Start and end block numbers of actual data on disk
  • If file is fragmented, will be a list of start/end fragments
• And many other things

Directory Data Structure

A file inode does not store the name of the file
Content of each directory is stored as a normal file in a block somewhere on disk

• Contains the filename of each file in the directory
• With each filename, it's corresponding inode number

Permissions and other metadata about each directory are stored in the inode that points to that directory data block
Since directories can be nested, some of the inodes listed in the directory block could point to other directory blocks (and so on)
Kernel has to follow a trail of inode numbers and block indexes before it can finally read the actual data blocks for a file

File Data Diagram

![[Pasted image 20250519022243.png]]

Deleting Files

When a file is deleted, its data blocks are not actually removed

• Writing over the data would waste a lot of time
• Only the inode will be deleted to remove the link to the data
• And the free list will be updated to record the data blocks as available

Files can be recovered using specialist software

• Recovery when files are deleted in error
• For criminal investigations (computer forensics) to recover evidence
• Only possible if the data blocks have not already been overwritten by a new file

Many operating systems provide secure delete and secure format facilities

• Completely erase a file or an entire disk
• Works by repeatedly writing random data to the relevant disk blocks

Symbolic Links (Hard and Soft)

A file can be given a second filename with the ln command (ln file1 file2)

• Files can be in different directories (but not different physical partitions)
• Adds file2's name to the relevant directory data file
• Along with file1's inode reference
• Known as a hard link
• A single inode is referenced from multiple directory entries

Or, a soft link can be created to the file ln -s file1 file2

• Creates a new file called file2 and stores file1's name in it
• Adds file2 and its new inode reference to the relevant directory data file
• Soft links can refer to files across different physical disks
• Adds a layer of indirection
• Each directory entry references a different inode

EXT4 Optimisation Features

• Journaling
  • Part of the disk is used to store a journal of changes made to inodes and data blocks
  • Changes are applied to disk after they're recorded in journal
  • Writing data is slower (writes everything twice)
  • Fast recovery from a system crash (only check and apply journal entries)
• Scattering
  • New files are spread evenly across the disk
  • Large gaps between each file
  • Allows room to grow contiguously
  • Reduces chance of files becoming fragmented
• Delayed Allocation
  • Created virtual blocks in memory while file is written
  • Commits to physical blocks when the final size is known
  • Allows system to find contiguous free space on disk
  • Could lose data if memory is not written to disk
  • Not always suitable for some users or situations (can be disabled for specific disks)
• Persistent pre-allocation
  • A system call (fallocate) can be used to reserve space for a file
  • All necessary blocks are allocated and filled with zeroes before real data arrives
  • Can be used to guarantee a contiguous set of blocks for the file
  • Improves read/write speed for media streaming and database applications

Standard File Streams

Every Linux system has three standard streams

• stdin - Standard input
• stdout - Standard output
• stderr - Standard error (where error messages are sent)
  For processes spawned by shell, these are linked to keyboard and terminal of the user
• Soft links created at /dev/stdin, /dev/stdout, /dev/stderr
• Point to entries in /proc/self (soft link to current process)
• All updated in the background as part of each context switch
  Since Linux treats everything as a file (using the same system calls)
• Can perform terminal I/O by reading and writing standard streams
• Can access virtual files associated with processes and devices
• Can read and write network sockets as if they were local files

File Descriptors

Every open file has a file descriptor (a positive integer)

• Used be system calls instead of file names
• File manager maps file descriptors onto physical files
• Recorded in the PCB of processes using the file
  Standard streams always have the same descriptors (stdin=0, stdout=1, stderr=2)
• Process details stored in a virtual directory
• Output stream of current process is a soft link to its file descriptor
• $ echo "Hello" > /proc/self/fd/1
• Hello
  The C printf and scanf subroutines are wrappers around system calls that use file descriptors 1 and 0 internally